In communication networks today, there is a need to build store-and-forward switches and routers that have line cards with high speeds. The line cards queue incoming traffic into memory, and subsequently dequeue the data from memory, as a prelude to its being sent to its destination. Each queue is associated with a flow (transfer of data from source to destination under certain parameters). The flow of data may be accomplished using any number of protocols including Asynchronous Transfer Mode (ATM), Internet Protocol (IP), and Transmission Control Protocol/IP (TCP/IP). The flows may be based on parameters such as the destination port of the packet, its source port, class of service, the protocol associated with the data. Therefore, a line card may maintain a large number of queues (e.g., one per flow).
The scheduling associated with the dequeuing of data can be done using a two-level hierarchical scheduler. In such a scheduler, a first level scheduler (a port-level scheduler) determines which of several eligible destination ports should be chosen to receive data from a given source port. A second lower-level scheduler (a queue level scheduler) chooses the individual queues that contain data for that destination port for dequeuing. The port-level scheduler often bases the decision of which destination port to transmit data to based on an aggregate count of data (e.g., bytes, words, packets) stored in the queues destined for each destination port. For example, when two line cards are attempting to send packets to the same destination port, the scheduler may give priority to the one that has larger amount of data (in aggregate) to send.
In order to generate the aggregate count the scheduler requests data counts for each queue associated with a destination every so often (e.g., every few clock cycles). As the requests are processed with other transactions, it may take several clock cycles before the count from each queue is received and the aggregate count can be generated. As data may be queued and dequeued each clock cycle, there is potential that the aggregate count is outdated as soon as it is received.
A further complicating factor is that some of the queues may be flow-controlled (flow control status OFF) and therefore not eligible to send data to the destination port. The data queued in such queues should not be included in the per-port counts used by the port-level scheduler. Therefore, the per queue counts of flow-controlled queues destined for each port should be excluded from the aggregate per-port count for the corresponding port. Additionally, when a queue transitions from an OFF (flow-controlled) state to an ON state and vice versa, the corresponding per-port counts need to be updated to include and exclude the queues respectively. Note that the queue for which the flow control state changes may be distinct from the queue for which data is being enqueued or dequeued, or it may be the same as one or both of these queues.
Using count requests to determine the aggregate count does not produce a real (or near real) time result and can thus provide outdated results that negatively effect the selection of the next queue.